Algoritmul RMQ poate fi abordat diferit in functie de caz cu urmatoarele complexitati 
pentru <construire,query>:

1. Trivial

* complexitate <O(N^2) , O(1)> si memorie O(N^2)
- este o dinamica usor de implementat
- recurenta: Rmq[i][j]= ( A[M[i][j-1]] < A[j] ) ? M[i][j-1] : j;
- query: A[Rmq[i][j]];



2. Crapare in sqrt

* complexitate <O(N) , O(sqrt(N))> si memorie O(N)
- usor de implementat si avantajos in cazul in care ai un N mare si Q mic
- de asemenea se economiseste multa memorie
- timp query: maxim 3*sqrt(N) 
- timp construire: constant O(N)



3. Sparse Table(ST) Clasic
- complexitate <O(N logN) , O(1)> si memorie O(N logN)
- RMQ clasic

- ideea se bazeaza pe faptul ca daca am calcula pt un interval [i,j] 
cel mai lung interval putere a lui 2 incepand din i spre dr cu capatul mai 
la st de j si cel mai lung interval putere a lui 2 incepand din j in 
st am rezolva problema

- recurenta: M[i][j] = A[M[i][j-1]] <= A[M[i+2<<(j-1)-1]] ? M[i][j-1] : M[i+2<<(j-1)-1][j-1];
- query: Rmq(i,j)=( A[M[i][k]] <= A[M[j-2<<k+1]] ) ? M[i][k] : M[j-2<<k+1][k] ; unde k=log(j-1+1);



4. Sparse Table(STM) Modificat 

- ineficient , dar usor implementabil
- complexitate <O(am(N) logN) , O(1)> si memorie O(N logN) , unde am(N) = N amortizat

- in cel mai defavorabil caz O(N* (logN ^ 2) )

- modficand recurenta putem obtine una mai simpla mergand de la coada la cap , deci recurenta va fi:
M[i][j] =  A[M[i][j+1]] <= A[j]  ? ( M[i][j+1]<j ? M[i][j+1]+1 : ver(i,j) ) : A[j]; 
unde ver(i,j) este spargerea in intervale a RMQ-ului 



Sursa 3:

#include <fstream>
using namespace std;

ifstream F("rmq.in");
ofstream G("rmq.out");

#define Dmax 1011
#define Log 12

int A[Dmax],N,M;
int D[Log][Dmax];
int Lg[Dmax];

int x,y;

#define v(x,y) ( D[Lg[y-x+1]][x] )
#define V(x,y) ( D[Lg[y-x+1]][y+1-1<<Lg[y-x+1]] )

#define Query(x,y) ( max( V(x,y) , v(x,y) ) )

int main()
{
	F>>N;
	
	for (int i=1;i<=N;++i) F>>A[i];
	for (int i=1;i<=N;++i) Lg[i]=( 1<<Lg[i-1] <i ) ? Lg[i-1] : Lg[i-1]+1 ;
	
	for (int i=1;i<=N;++i) D[0][i]=A[i];
	for (int k=1;k<=Lg[N];++k) 
		for (int i=1;i<=N;++i)
			D[k][i]=max( D[k-1][i] , D[k-1][i+1<<k-k] );
	
	F>>M;
	for (;M;--M)
		F>>x>>y , G<<Query(x,y)<<'\n';
	
}
